/* Copyright (c) 2006 by M Aamir Maniar 
 * 
 * Permission is hereby granted, free of charge, to any person obtaining 
 * a copy of this software and associated documentation files (the 
 * "Software"), to deal in the Software without restriction, including 
 * without limitation the rights to use, copy, modify, merge, publish, 
 * distribute, sublicense, and/or sell copies of the Software, and to 
 * permit persons to whom the Software is furnished to do so, subject to 
 * the following conditions:
 * 
 * The above copyright notice and this permission notice shall be 
 * included in all copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 * 
 * */

namespace Generic.DataStructures.Trees
{
	using System;
	using System.Collections.Generic;
	using System.Text;

    //TODO:Not complete code
    public class BinaryTree<T> : IEnumerable<T> // : ICollection<T>
    {
        #region public BinaryTree()
        /// <summary>
        /// Initializes a new instance of the <see cref="BinaryTree&lt;T&gt;"/> class.
        /// </summary>
        public BinaryTree()
        {
            
        }
        #endregion

        #region public BinaryTree(BinaryTreeNode<T> rootNode, IComparer<T> comparer)
        /// <summary>
        /// Initializes a new instance of the <see cref="BinaryTree&lt;T&gt;"/> class.
        /// </summary>
        /// <param name="rootNode">The root node.</param>
        /// <param name="comparer">The comparer.</param>
        public BinaryTree(BinaryTreeNode<T> rootNode, IComparer<T> comparer)
        {
            if (comparer == null)
            {
                if ((rootNode.Value is IComparable) || (rootNode.Value is IComparable<T>))
                {
                    //_depth = new BinaryTreeNodeDepth<T>(this);
                }
                else
                {
                    throw new InvalidOperationException("Either T is not comparable or IComparer<T> is not supplied");
                }
            }
        }
        #endregion

        #region public BinaryTree(T rootNodeValue): this(new BinaryTreeNode<T>(rootNodeValue))
        /// <summary>
        /// Initializes a new instance of the <see cref="BinaryTree&lt;T&gt;"/> class.
        /// </summary>
        /// <param name="rootNodeValue">The root node value.</param>
        public BinaryTree(T rootNodeValue): this(new BinaryTreeNode<T>(rootNodeValue), null)
        {
        }
        #endregion

        #region public BinaryTreeNode<T> Root
        private BinaryTreeNode<T> _root;
        /// <summary>
        /// Gets or sets the root.
        /// </summary>
        /// <value>The root.</value>
		public BinaryTreeNode<T> Root
		{
			get { return _root; }
			set { _root = value; }
        }
        #endregion

        #region public BinaryTreeNode<T> Find(BinaryTreeNode<T> treeNode)
        /// <summary>
        /// Finds the specified tree node.
        /// </summary>
        /// <param name="treeNode">The tree node.</param>
        /// <returns></returns>
        public BinaryTreeNode<T> Find(BinaryTreeNode<T> treeNode)
        {
            return Find(treeNode.Value);
        }
        #endregion

        #region public virtual BinaryTreeNode<T> Find(T value)
        /// <summary>
        /// Finds the specified value.
        /// </summary>
        /// <param name="value">The value.</param>
        /// <returns></returns>
        public virtual BinaryTreeNode<T> Find(T value)
        {
            return FindInSubTree(Root, value);
        }
        #endregion

        #region public BinaryTreeNodeDepth<T> Depth        
        /// <summary>
        /// Gets the depth.
        /// </summary>
        /// <value>The depth.</value>
        public int Depth
        {
            get 
            {
                return BinaryTreeNode<T>.CalculateExactDepth(_root, 1); 
            }
        }
        #endregion

        #region public bool IsBalanced
        /// <summary>
        /// Gets a value indicating whether this instance is balanced.
        /// </summary>
        /// <value>
        /// 	<c>true</c> if this instance is balanced; otherwise, <c>false</c>.
        /// </value>
        public bool IsBalanced
        {
            get
            {
                return false;
            }
        }
        #endregion

        #region IEnumerable<T> Members

        public IEnumerator<T> GetEnumerator()
        {
            throw new Exception("The method or operation is not implemented.");
        }

        #endregion

        #region IEnumerable Members

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            throw new Exception("The method or operation is not implemented.");
        }

        #endregion

        #region ICollection<T> Members

        /// <summary>
        /// Adds an item to the <see cref="T:BinaryTree<T>"></see>.
        /// </summary>
        /// <param name="item">The node to add to the <see cref="T:BinaryTree<T>"></see>.</param>
        /// <param name="node">The node.</param>
        public void Add(BinaryTreeNode<T> node)
        {
            if (node == null)
                throw new NullReferenceException();

            BinaryTreeNode<T> parentNode = null;
            BinaryTreeNode<T> currentNode = Root;
            
            while (currentNode != null) //Find ParentNode
            {
                parentNode = currentNode;
                if (node < currentNode)
                    currentNode = currentNode.LeftChild;
                else
                    currentNode = currentNode.RightChild;
            }
            
            node.Parent = parentNode;

            if (parentNode == null)
                Root = node;
            else if (node < parentNode)
                parentNode.LeftChild = node;
            else
                parentNode.RightChild = node;
            node.BinaryTree = this;
            _count++;
        }

        /// <summary>
        /// Adds an item to the <see cref="T:System.Collections.Generic.ICollection`1"></see>.
        /// </summary>
        /// <param name="item">The object to add to the <see cref="T:System.Collections.Generic.ICollection`1"></see>.</param>
        public void Add(T item)
        {
            BinaryTreeNode<T> newNode = new BinaryTreeNode<T>(item);
            Add(newNode);
        }

        /// <summary>
        /// Removes all items from the <see cref="T:System.Collections.Generic.ICollection`1"></see>.
        /// </summary>
        /// <exception cref="T:System.NotSupportedException">The <see cref="T:System.Collections.Generic.ICollection`1"></see> is read-only. </exception>
        public void Clear()
        {
            ClearSubTree(Root);
        }

        /// <summary>
        /// Determines whether the <see cref="T:System.Collections.Generic.ICollection`1"></see> contains a specific value.
        /// </summary>
        /// <param name="item">The object to locate in the <see cref="T:System.Collections.Generic.ICollection`1"></see>.</param>
        /// <returns>
        /// true if item is found in the <see cref="T:System.Collections.Generic.ICollection`1"></see>; otherwise, false.
        /// </returns>
        public bool Contains(T item)
        {
            if (FindInSubTree(Root, item) != null)
            {
                return true;
            }
            else
            {
                return false;
            }
        }

        /// <summary>
        /// Copies the elements of the <see cref="T:System.Collections.Generic.ICollection`1"></see> to an <see cref="T:System.Array"></see>, starting at a particular <see cref="T:System.Array"></see> index.
        /// </summary>
        /// <param name="array">The one-dimensional <see cref="T:System.Array"></see> that is the destination of the elements copied from <see cref="T:System.Collections.Generic.ICollection`1"></see>. The <see cref="T:System.Array"></see> must have zero-based indexing.</param>
        /// <param name="arrayIndex">The zero-based index in array at which copying begins.</param>
        /// <exception cref="T:System.ArgumentOutOfRangeException">arrayIndex is less than 0.</exception>
        /// <exception cref="T:System.ArgumentNullException">array is null.</exception>
        /// <exception cref="T:System.ArgumentException">array is multidimensional.-or-arrayIndex is equal to or greater than the length of array.-or-The number of elements in the source <see cref="T:System.Collections.Generic.ICollection`1"></see> is greater than the available space from arrayIndex to the end of the destination array.-or-Type T cannot be cast automatically to the type of the destination array.</exception>
        public void CopyTo(IList<T> array, int arrayIndex)
        {
            throw new Exception("The method or operation is not implemented.");
        }

        int _count = 0;
        /// <summary>
        /// Gets the number of elements contained in the <see cref="T:System.Collections.Generic.ICollection`1"></see>.
        /// </summary>
        /// <value></value>
        /// <returns>The number of elements contained in the <see cref="T:System.Collections.Generic.ICollection`1"></see>.</returns>
        public int Count
        {
            get 
            {
                return _count;
            }
        }

        /// <summary>
        /// Gets a value indicating whether the <see cref="T:System.Collections.Generic.ICollection`1"></see> is read-only.
        /// </summary>
        /// <value></value>
        /// <returns>true if the <see cref="T:System.Collections.Generic.ICollection`1"></see> is read-only; otherwise, false.</returns>
        public bool IsReadOnly
        {
            get { return false; }
        }

        /// <summary>
        /// Removes the first occurrence of a specific object from the <see cref="T:System.Collections.Generic.ICollection`1"></see>.
        /// </summary>
        /// <param name="item">The object to remove from the <see cref="T:System.Collections.Generic.ICollection`1"></see>.</param>
        /// <returns>
        /// true if item was successfully removed from the <see cref="T:System.Collections.Generic.ICollection`1"></see>; otherwise, false. This method also returns false if item is not found in the original <see cref="T:System.Collections.Generic.ICollection`1"></see>.
        /// </returns>
        /// <exception cref="T:System.NotSupportedException">The <see cref="T:System.Collections.Generic.ICollection`1"></see> is read-only.</exception>
        public bool Remove(T item)
        {
            throw new Exception("The method or operation is not implemented.");
        }

        #endregion

        #region protected void ClearSubTree(BinaryTreeNode<T> node)
        /// <summary>
        /// Clears the sub tree.
        /// </summary>
        /// <param name="node">The node.</param>
        protected void ClearSubTree(BinaryTreeNode<T> node)
        {
            if (node != null)
            {
                ClearSubTree(node.LeftChild);
                ClearSubTree(node.RightChild);
                if (node is IDisposable)
                {
                    ((IDisposable)node.Value).Dispose();
                }
                node = null;
            }
        }
        #endregion

        #region protected BinaryTreeNode<T> FindInSubTree(BinaryTreeNode<T> node, T value)
        /// <summary>
        /// Finds given value in specified sbu TreeNode.
        /// </summary>
        /// <param name="node">The node.</param>
        /// <param name="value">The value.</param>
        /// <returns></returns>
        protected BinaryTreeNode<T> FindInSubTree(BinaryTreeNode<T> node, T value)
        {
            if (node == null || node.Value == null)
            {
                return null;
            }
            if (node.CompareTo(value) == 0)
            {
                return node;
            }
            else if (node.CompareTo(value) < 0)
            {
                return FindInSubTree(node.LeftChild, value);
            }
            else
            {
                return FindInSubTree(node.RightChild, value);
            }
        }
        #endregion

    }
}
